The present invention relates to a data processing device used in the virtual memory method which is one of memory control methods for computer systems. This data processing device is used where a paging system is employed to implement the virtual memory method.
A paging system is a system as described below. A program and/or, data and a storage region of a main memory are each divided into sections having the same size. The unit to which the program and/or data are divided is referred to as a page, and the unit to which the storage region is divided is referred to as a page frame. When the program is executed by a CPU, necessary pages are first loaded from an external memory into page frames in the main memory (page-in) and are executed. Thereafter, if any necessary page exists in a page frame in the memory, the page is executed as it is. Conversely, if there is no necessary page in the page frames in the main memory (this state is referred to as "page fault"), after any page on the main memory is shifted to the external memory (page-out), necessary pages are shifted from the external memory into the main memory (page-in) and are executed. Such page-in and page-out operations are referred to as paging.
As a logic for selecting pages to be paged out, an LRU (last-recently-used) paging process is used Wherein pages which are less frequently referred to are paged out. On the other hand, the increasing demands for computer systems having higher speeds in recent years call for a paging system with less overhead. Therefore, there is a need in the art to improve the LRU paging system in order to construct data processing devices which allow paging at higher speeds.
The present invention relates to such a data processing device for performing paging at a high speed.
FIG. 12 shows a conventional configuration for LRU paging.
In FIG. 12, a storage region of a main memory 110 is divided into a plurality of page frames 110a. Pages that constitute a program or data are loaded for each of the page frames 110a. Each of the page frames 110a has a flag region 110b wherein a reference flag indicating whether the page written therein has been referred to and a seizure inhibition flag indicating that the page is a page which cannot be seized from the page frame 110a are set and has an LRU counter region 110c for keeping a counter value indicating the time period during which the page written therein has not been referred to.
In association with the main memory 110 having such a configuration, there are provided a memory access monitoring mechanism 111 implemented with hardware, an LRU counter setting section 112 implemented with software, a seizable page judging section 113 implemented with software and a page contents saving section 114 implemented with software.
When a page is referred to, the memory access monitoring section 111 sets a reference flag in the page 110a corresponding to the page referred to.
The LRU counter setting section 112 has a timer. Each time the timer reaches a defined period, the LRU counter setting section 112 scans each of the page frames 110a and detects whether there is a reference flag or not. According to the state of reference flag setting, the LRU counter setting section 112 rewrites the counter value kept in the LRU counter region 110c to increment it if the page written in the page frame scanned has not been referred to. On the other hand, if the page written in the page frame scanned has been referred to, the LRU counter setting section 112 clears the counter value kept in the LRU counter region 110c and clears the reference flag. When a page fault occurs, the seizable page judging section 113 judges the page to be seized on the basis of the counter value thereof. The page contents saving section 114 pages out the page which has been seized to the external memory.
In this conventional data processing device, in order to judge the page to be seized, the seizable page judging section 113 first scans the LRU counter value and reference flag of each page. If there is a page having the maximum LRU counter value among all pages stored in the main memory 110, the seized page judging section 113 judges such a page to be seized provided that it is a page which is seizable. An seizable page as used here means a page wherein a reference flag as described above is not found to be set during the reference made to scan the LRU counter value and is an object for referring by its nature on the contrary, a page which is not an object for referring by its nature is such as a page at an area wherein an I/O device is in unsynchronous connection with a CPU. For such a page which is not to be referred to by its nature, an seizure inhibition flag is set in advance.
Since paging is normally able to handle a plurality of pages at a time to increase processing speed, a CPU (not shown) issues a command directing to page out a plurality of pages together depending on the number of pages to be written. However, the seized page judging section 13 judges pages whose LRU counter values are equal to the preset maximum value to be objects of seizure in one cycle of scanning. Therefore, the required number of pages may not be acquired in one cycle of scanning. In this case, scanning is similarly repeated after the first scannning. This time, pages which have an LRU counter value smaller by one than the LRU counter value for the pages judged to be objects of seizure in the first process and which is seizable, are judged to be objects of seizure. If the requested number of pages can not be acquired in this scanning, the similar scanning is repeated further to judge pages which have an LRU counter value further smaller by one and which is seizable as objects of seizure. Conventional data processing devices employ a system wherein such a procedure is repeated to judge the requested number of pages as objects of seizure.
In this regard, a specific example will be described with reference to FIG. 2.
It is assumed for FIG. 2 that particular numerical values are kept in the flag region 110b and the LRU counter region 110c of the main memory 110. It is assumed that this device is preset to page six pages at a time when a page fault occurs. The LRU counter value is assumed to be within the range from "0" to "5".
Assume that a CPU (not shown) accessed the main memory 110 and it was judged that a page fault occurred because there was no hit on the program or data required. In this case, the seized page judging section 113 is requested to page out 6 pages.
The seized page judging section 113 first examines all pages one by one to see whether their respective LRU count values are equal to "5" or not. In this cycle of scanning, only two pages, i.e., Page 7 and Page 10 are acquired as pages to be seized. However, the requested number of pages "6" has not been reached with the total number of the decided pages.
Next, the seized page judging section 113 examines all pages to see whether their respective LRU count values are equal to "4" or not. In this cycle of scanning, only one page, i.e., Page 9 is acquired as a page to be seized (Page 11 is excluded from objects of seizure because it has a reference flag set.). At this point, the total number of pages acquired is "3" but is still short of the requested number of pages of "6".
Then, the seized page judging section 113 examines all pages to see whether their respective LRU count values are equal to "3" or not. In this cycle of scanning, three pages, i.e., Page 4, Page 6 and Page 15 are acquired as pages to be seized. This brings about the total number of pages acquired "6", and the requested number of pages "6" is reached.
Thus, the requested number of pages "6" is finally acquired and it is now possible to perform page-out with the page contents saving section 114.
However, according to the conventional art wherein scanning is performed through the LRU counter values one by one in the order of decreasing values, it takes a long time to judge the pages to be seized. Scanning is performed on the LRU counter value of each page in the order of decreasing values even when the distribution of the LRU counter values is biased toward lower values. As a result, the time required for judging the pages to be seized becomes especially long.
In the worst case, the scanning of the LRU counter values of all pages must be repeated from the maximum value to the minimum value of the LRU counter values.